SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Recursion</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Recursion</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For other uses, see <a href="Recursion_(disambiguation)" class="mw-disambig" title="Recursion (disambiguation)">Recursion (disambiguation)</a>.</div>

</p>

<p><b>Recursion</b> occurs when the definition of a concept or process depends on a simpler or previous version of itself.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Recursion is used in a variety of disciplines ranging from <a href="Linguistics" title="Linguistics">linguistics</a> to <a href="Logic" title="Logic">logic</a>. The most common application of recursion is in <a href="Mathematics" title="Mathematics">mathematics</a> and <a href="Computer_science" title="Computer science">computer science</a>, where a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> being defined is applied within its own definition. While this apparently defines an infinite number of instances (function values), it is often done in such a way that no infinite loop or infinite chain of references can occur.

</p><p>A process that exhibits recursion is <i>recursive</i>. <a href="Video_feedback" title="Video feedback">Video feedback</a> displays recursive images, as does an <a href="Infinity_mirror" title="Infinity mirror">infinity mirror</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_definitions">Formal definitions</h2></div>

<p>In mathematics and computer science, a class of objects or methods exhibits recursive behavior when it can be defined by two properties:

</p>

<ul><li>A simple <i>base case</i> (or cases) — a terminating scenario that does not use recursion to produce an answer</li>

<li>A <i>recursive step</i> — a set of rules that reduces all successive cases toward the base case.</li></ul>

<p>For example, the following is a recursive definition of a person's <i>ancestor</i>. One's ancestor is either:

</p>

<ul><li>One's parent (<i>base case</i>), <i>or</i></li>

<li>One's parent's ancestor (<i>recursive step</i>).</li></ul>

<p>The <a href="Fibonacci_sequence" title="Fibonacci sequence">Fibonacci sequence</a> is another classic example of recursion:

</p>

<dl><dd>For all <a href="Integer" title="Integer">integers</a> <span class="texhtml"><i>n</i> > 1</span>, <span class="texhtml">Fib(<i>n</i>) = Fib(<i>n</i> − 1) + Fib(<i>n</i> − 2)</span>.</dd></dl>

<p>Many mathematical axioms are based upon recursive rules. For example, the formal definition of the <a href="Natural_number" title="Natural number">natural numbers</a> by the <a href="Peano_axioms" title="Peano axioms">Peano axioms</a> can be described as: "Zero is a natural number, and each natural number has a successor, which is also a natural number."<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> By this base case and recursive rule, one can generate the set of all natural numbers.

</p><p>Other recursively defined mathematical objects include <a href="Factorial" title="Factorial">factorials</a>, <a href="Function_(mathematics)" title="Function (mathematics)">functions</a> (e.g., <a href="Recurrence_relation" title="Recurrence relation">recurrence relations</a>), <a href="Set_(mathematics)" title="Set (mathematics)">sets</a> (e.g., <a href="Cantor_ternary_set" class="mw-redirect" title="Cantor ternary set">Cantor ternary set</a>), and <a href="Fractal" title="Fractal">fractals</a>.

</p><p>There are various more tongue-in-cheek definitions of recursion; see <a href="#Recursive_humor">recursive humor</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Informal_definition">Informal definition</h2></div>

<p>Recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself. A procedure that goes through recursion is said to be 'recursive'.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>To understand recursion, one must recognize the distinction between a procedure and the running of a procedure. A procedure is a set of steps based on a set of rules, while the running of a procedure involves actually following the rules and performing the steps.

</p><p>Recursion is related to, but not the same as, a reference within the specification of a procedure to the execution of some other procedure.

</p><p>When a procedure is thus defined, this immediately creates the possibility of an endless loop; recursion can only be properly used in a definition if the step in question is skipped in certain cases so that the procedure can complete.

</p><p>Even if it is properly defined, a recursive procedure is not easy for humans to perform, as it requires distinguishing the new from the old, partially executed invocation of the procedure; this requires some administration as to how far various simultaneous instances of the procedures have progressed. For this reason, recursive definitions are very rare in everyday situations.

</p>

<div class="mw-heading mw-heading2"><h2 id="In_language">In language</h2></div>

<p>Linguist <a href="Noam_Chomsky" title="Noam Chomsky">Noam Chomsky</a>, among many others, has argued that the lack of an upper bound on the number of grammatical sentences in a language, and the lack of an upper bound on grammatical sentence length (beyond practical constraints such as the time available to utter one), can be explained as the consequence of recursion in natural language.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>This can be understood in terms of a recursive definition of a syntactic category, such as a sentence. A sentence can have a structure in which what follows the verb is another sentence: <i>Dorothy thinks witches are dangerous</i>, in which the sentence <i>witches are dangerous</i> occurs in the larger one. So a sentence can be defined recursively (very roughly) as something with a structure that includes a noun phrase, a verb, and optionally another sentence. This is really just a special case of the mathematical definition of recursion.

</p><p>This provides a way of understanding the creativity of language—the unbounded number of grammatical sentences—because it immediately predicts that sentences can be of arbitrary length: <i>Dorothy thinks that Toto suspects that Tin Man said that...</i>. There are many structures apart from sentences that can be defined recursively, and therefore many ways in which a sentence can embed instances of one category inside another.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> Over the years, languages in general have proved amenable to this kind of analysis.

</p><p>The generally accepted idea that recursion is an essential property of human language has been challenged by <a href="Daniel_Everett" title="Daniel Everett">Daniel Everett</a> on the basis of his claims about the <a href="Pirah%C3%A3_language" title="Pirahã language">Pirahã language</a>. Andrew Nevins, David Pesetsky and Cilene Rodrigues are among many who have argued against this.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Literary <a href="Self-reference" title="Self-reference">self-reference</a> can in any case be argued to be different in kind from mathematical or logical recursion.<sup id="cite_ref-Drucker2008_8-0" class="reference"><a href="#cite_note-Drucker2008-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>Recursion plays a crucial role not only in syntax, but also in <a href="Natural_language_semantics" class="mw-redirect" title="Natural language semantics">natural language semantics</a>. The word <i>and</i>, for example, can be construed as a function that can apply to sentence meanings to create new sentences, and likewise for noun phrase meanings, verb phrase meanings, and others. It can also apply to intransitive verbs, transitive verbs, or ditransitive verbs. In order to provide a single denotation for it that is suitably flexible, <i>and</i> is typically defined so that it can take any of these different types of meanings as arguments. This can be done by defining it for a simple case in which it combines sentences, and then defining the other cases recursively in terms of the simple one.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p><p>A <a href="Recursive_grammar" title="Recursive grammar">recursive grammar</a> is a <a href="Formal_grammar" title="Formal grammar">formal grammar</a> that contains recursive <a href="Production_(computer_science)" title="Production (computer science)">production rules</a>.<sup id="cite_ref-ns02_10-0" class="reference"><a href="#cite_note-ns02-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Recursive_humor">Recursive humor</h3></div>

<p>Recursion is sometimes used humorously in computer science, programming, philosophy, or mathematics textbooks, generally by giving a <a href="Circular_definition" title="Circular definition">circular definition</a> or <a href="Self-reference" title="Self-reference">self-reference</a>, in which the putative recursive step does not get closer to a base case, but instead leads to an <a href="Infinite_regress" title="Infinite regress">infinite regress</a>. It is not unusual for such books to include a joke entry in their glossary along the lines of:

</p>

<dl><dd>Recursion, <i>see Recursion</i>.<sup id="cite_ref-Hunter_11-0" class="reference"><a href="#cite_note-Hunter-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></dd></dl>

<p>A variation is found on page 269 in the <a href="Back-of-the-book_index" class="mw-redirect" title="Back-of-the-book index">index</a> of some editions of <a href="Brian_Kernighan" title="Brian Kernighan">Brian Kernighan</a> and <a href="Dennis_Ritchie" title="Dennis Ritchie">Dennis Ritchie</a>'s book <i><a href="The_C_Programming_Language" title="The C Programming Language">The C Programming Language</a></i>; the index entry recursively references itself ("recursion 86, 139, 141, 182, 202, 269"). Early versions of this joke can be found in <i>Let's talk Lisp</i> by Laurent Siklóssy (published by Prentice Hall PTR on December 1, 1975, with a copyright date of 1976) and in <i>Software Tools</i> by Kernighan and Plauger (published by Addison-Wesley Professional on January 11, 1976). The joke also appears in <i>The UNIX Programming Environment</i> by Kernighan and Pike. It did not appear in the first edition of <i>The C Programming Language</i>. The joke is part of the <a href="Functional_programming" title="Functional programming">functional programming</a> folklore and was already widespread in the functional programming community before the publication of the aforementioned books. <sup id="cite_ref-Grainger_College_12-0" class="reference"><a href="#cite_note-Grainger_College-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Columbia_University_13-0" class="reference"><a href="#cite_note-Columbia_University-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>

</p>

<p>Another joke is that "To understand recursion, you must understand recursion."<sup id="cite_ref-Hunter_11-1" class="reference"><a href="#cite_note-Hunter-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> In the English-language version of the Google web search engine, when a search for "recursion" is made, the site suggests "Did you mean: <i>recursion</i>."<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> An alternative form is the following, from <a href="Andrew_Plotkin" title="Andrew Plotkin">Andrew Plotkin</a>: <i>"If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to <a href="Douglas_Hofstadter" title="Douglas Hofstadter">Douglas Hofstadter</a> than you are; then ask him or her what recursion is."</i>

</p><p><a href="Recursive_acronym" title="Recursive acronym">Recursive acronyms</a> are other examples of recursive humor. <a href="PHP" title="PHP">PHP</a>, for example, stands for "PHP Hypertext Preprocessor", <a href="Wine_(software)" title="Wine (software)">WINE</a> stands for "WINE Is Not an Emulator", <a href="GNU" title="GNU">GNU</a> stands for "GNU's not Unix", and <a href="SPARQL" title="SPARQL">SPARQL</a> denotes the "SPARQL Protocol and RDF Query Language".

</p>

<div class="mw-heading mw-heading2"><h2 id="In_mathematics">In mathematics</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Recursively_defined_sets">Recursively defined sets</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Recursive_definition" title="Recursive definition">Recursive definition</a></div>

<div class="mw-heading mw-heading4"><h4 id="Example:_the_natural_numbers">Example: the natural numbers</h4></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Closure_(mathematics)" title="Closure (mathematics)">Closure (mathematics)</a></div>

<p>The canonical example of a recursively defined set is given by the <a href="Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a>:

</p>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./fdf9a96b565ea202d0f4322e9195613fb26a9bed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" loading="lazy"></span>, then <i>n</i> + 1 is in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

<dd>The set of natural numbers is the smallest set satisfying the previous two properties.</dd></dl>

<p>In mathematical logic, the <a href="Peano_axioms" title="Peano axioms">Peano axioms</a> (or Peano postulates or Dedekind–Peano axioms), are axioms for the natural numbers presented in the 19th century by the German mathematician <a href="Richard_Dedekind" title="Richard Dedekind">Richard Dedekind</a> and by the Italian mathematician <a href="Giuseppe_Peano" title="Giuseppe Peano">Giuseppe Peano</a>. The Peano Axioms define the natural numbers referring to a recursive successor function and addition and multiplication as recursive functions.

</p>

<div class="mw-heading mw-heading4"><h4 id="Example:_Proof_procedure">Example: Proof procedure</h4></div>

<p>Another interesting example is the set of all "provable" propositions in an <a href="Axiomatic_system" title="Axiomatic system">axiomatic system</a> that are defined in terms of a <a href="Proof_procedure" title="Proof procedure">proof procedure</a> which is inductively (or recursively) defined as follows:

</p>

<ul><li>If a proposition is an axiom, it is a provable proposition.</li>

<li>If a proposition can be derived from true reachable propositions by means of inference rules, it is a provable proposition.</li>

<li>The set of provable propositions is the smallest set of propositions satisfying these conditions.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Finite_subdivision_rules">Finite subdivision rules</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Finite_subdivision_rule" title="Finite subdivision rule">Finite subdivision rule</a></div>

<p>Finite subdivision rules are a geometric form of recursion, which can be used to create fractal-like images. A subdivision rule starts with a collection of polygons labelled by finitely many labels, and then each polygon is subdivided into smaller labelled polygons in a way that depends only on the labels of the original polygon. This process can be iterated. The standard `middle thirds' technique for creating the <a href="Cantor_set" title="Cantor set">Cantor set</a> is a subdivision rule, as is <a href="Barycentric_subdivision" title="Barycentric subdivision">barycentric subdivision</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Functional_recursion">Functional recursion</h3></div>

<p>A <a href="Function_(mathematics)" title="Function (mathematics)">function</a> may be recursively defined in terms of itself. A familiar example is the <a href="Fibonacci_number" class="mw-redirect" title="Fibonacci number">Fibonacci number</a> sequence: <i>F</i>(<i>n</i>) = <i>F</i>(<i>n</i> − 1) + <i>F</i>(<i>n</i> − 2). For such a definition to be useful, it must be reducible to non-recursively defined values: in this case <i>F</i>(0) = 0 and <i>F</i>(1) = 1.

</p>

<div class="mw-heading mw-heading3"><h3 id="Proofs_involving_recursive_definitions">Proofs involving recursive definitions</h3></div>

<p>Applying the standard technique of <a href="Proof_by_cases" class="mw-redirect" title="Proof by cases">proof by cases</a> to recursively defined sets or functions, as in the preceding sections, yields <a href="Structural_induction" title="Structural induction">structural induction</a> — a powerful generalization of <a href="Mathematical_induction" title="Mathematical induction">mathematical induction</a> widely used to derive proofs in <a href="Mathematical_logic" title="Mathematical logic">mathematical logic</a> and computer science.

</p>

<div class="mw-heading mw-heading3"><h3 id="Recursive_optimization">Recursive optimization</h3></div>

<p><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a> is an approach to <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization</a> that restates a multiperiod or multistep optimization problem in recursive form. The key result in dynamic programming is the <a href="Bellman_equation" title="Bellman equation">Bellman equation</a>, which writes the value of the optimization problem at an earlier time (or earlier step) in terms of its value at a later time (or later step).

</p>

<div class="mw-heading mw-heading3"><h3 id="The_recursion_theorem">The recursion theorem</h3></div>

<p>In <a href="Set_theory" title="Set theory">set theory</a>, this is a theorem guaranteeing that recursively defined functions exist. Given a set <span class="texhtml mvar" style="font-style:italic;">X</span>, an element <span class="texhtml mvar" style="font-style:italic;">a</span> of <span class="texhtml mvar" style="font-style:italic;">X</span> and a function <span class="texhtml"><i>f</i>: <i>X</i> → <i>X</i></span>, the theorem states that there is a unique function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F:\mathbb {N} \to X}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F:\mathbb {N} \to X}</annotation>

</semantics>

</math></span><img src="./12e26c5d663cc5a24ab3ceef0bf75ad2c7c626e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.95ex; height:2.176ex;" alt="{\displaystyle F:\mathbb {N} \to X}" loading="lazy"></span> (where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(0)=a}</annotation>

</semantics>

</math></span><img src="./e13d054d8df6f9f2770997b66344c4f390bae2d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.041ex; height:2.843ex;" alt="{\displaystyle F(0)=a}" loading="lazy"></span></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(n+1)=f(F(n))}</annotation>

</semantics>

</math></span><img src="./872fa88af5e4b3ca934ba4abee41be187e3d3f94.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.079ex; height:2.843ex;" alt="{\displaystyle F(n+1)=f(F(n))}" loading="lazy"></span></dd></dl>

<p>for any natural number <span class="texhtml mvar" style="font-style:italic;">n</span>.

</p><p>Dedekind was the first to pose the problem of unique definition of set-theoretical functions on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./fdf9a96b565ea202d0f4322e9195613fb26a9bed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" loading="lazy"></span> by recursion, and gave a sketch of an argument in the 1888 essay "Was sind und was sollen die Zahlen?" <sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Proof_of_uniqueness">Proof of uniqueness</h4></div>

<p>Take two functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F:\mathbb {N} \to X}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F:\mathbb {N} \to X}</annotation>

</semantics>

</math></span><img src="./12e26c5d663cc5a24ab3ceef0bf75ad2c7c626e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.95ex; height:2.176ex;" alt="{\displaystyle F:\mathbb {N} \to X}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G:\mathbb {N} \to X}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G:\mathbb {N} \to X}</annotation>

</semantics>

</math></span><img src="./23a0594749da30b07c384d71c20068c54f02af5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.036ex; height:2.176ex;" alt="{\displaystyle G:\mathbb {N} \to X}" loading="lazy"></span> such that:

</p>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(0)=a}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(0)=a}</annotation>

</semantics>

</math></span><img src="./1e4144e1a9d47560e0b5930da11b91807bde69f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.127ex; height:2.843ex;" alt="{\displaystyle G(0)=a}" loading="lazy"></span></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F(n+1)=f(F(n))}</annotation>

</semantics>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(n+1)=f(G(n))}</annotation>

</semantics>

</math></span><img src="./e0c178891ef17320110f41eaeb21ab5307f996a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.251ex; height:2.843ex;" alt="{\displaystyle G(n+1)=f(G(n))}" loading="lazy"></span></dd></dl>

<p>where <span class="texhtml mvar" style="font-style:italic;">a</span> is an element of <span class="texhtml mvar" style="font-style:italic;">X</span>.

</p><p>It can be proved by <a href="Mathematical_induction" title="Mathematical induction">mathematical induction</a> that <span class="texhtml"><i>F</i>(<i>n</i>) = <i>G</i>(<i>n</i>)</span> for all natural numbers

<span class="texhtml mvar" style="font-style:italic;">n</span>:

</p>

<dl><dd><b>Base Case</b>: <span class="texhtml"><i>F</i>(0) = <i>a</i> = <i>G</i>(0)</span> so the equality holds for <span class="texhtml"><i>n</i> = 0</span>.</dd></dl>

<dl><dd><b>Inductive Step</b>: Suppose <span class="texhtml"><i>F</i>(<i>k</i>) = <i>G</i>(<i>k</i>)</span> for some <span class="nowrap"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./2a5bc4b7383031ba693b7433198ead7170954c1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.73ex; height:2.176ex;" alt="{\displaystyle k\in \mathbb {N} }" loading="lazy"></span>.</span> Then <span class="texhtml"><i>F</i>(<i>k</i> + 1) = <i>f</i>(<i>F</i>(<i>k</i>)) = <i>f</i>(<i>G</i>(<i>k</i>)) = <i>G</i>(<i>k</i> + 1)</span>.

<dl><dd>Hence <span class="texhtml"><i>F</i>(<i>k</i>) = <i>G</i>(<i>k</i>)</span> implies <span class="texhtml"><i>F</i>(<i>k</i> + 1) = <i>G</i>(<i>k</i> + 1)</span>.</dd></dl></dd></dl>

<p>By induction, <span class="texhtml"><i>F</i>(<i>n</i>) = <i>G</i>(<i>n</i>)</span> for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./d059936e77a2d707e9ee0a1d9575a1d693ce5d0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle n\in \mathbb {N} }" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="In_computer_science">In computer science</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Recursion_(computer_science)" title="Recursion (computer science)">Recursion (computer science)</a></div>

<p>A common method of simplification is to divide a problem into subproblems of the same type. As a <a href="Computer_programming" title="Computer programming">computer programming</a> technique, this is called <a href="Divide_and_conquer_algorithm" class="mw-redirect" title="Divide and conquer algorithm">divide and conquer</a> and is key to the design of many important algorithms. Divide and conquer serves as a top-down approach to problem solving, where problems are solved by solving smaller and smaller instances. A contrary approach is <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>. This approach serves as a bottom-up approach, where problems are solved by solving larger and larger instances, until the desired size is reached.

</p><p>A classic example of recursion is the definition of the <a href="Factorial" title="Factorial">factorial</a> function, given here in <a href="Python_(programming_language)" title="Python (programming language)">Python</a> code:

</p>

<div class="mw-highlight mw-highlight-lang-python3 mw-content-ltr" dir="ltr"><pre><span class="k">def</span><span class="w"> </span><span class="nf">factorial</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>

<span class="k">return</span> <span class="n">n</span> <span class="o">*</span> <span class="n">factorial</span><span class="p">(</span><span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>

<span class="k">return</span> <span class="mi">1</span>

</pre></div>

<p>The function calls itself recursively on a smaller version of the input <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">(n - 1)</code> and multiplies the result of the recursive call by <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">n</code>, until reaching the <a href="Base_case_(recursion)" class="mw-redirect" title="Base case (recursion)">base case</a>, analogously to the mathematical definition of factorial.

</p><p>Recursion in computer programming is exemplified when a function is defined in terms of simpler, often smaller versions of itself. The solution to the problem is then devised by combining the solutions obtained from the simpler versions of the problem. One example application of recursion is in <a href="Parser" class="mw-redirect" title="Parser">parsers</a> for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.

</p><p><a href="Recurrence_relation" title="Recurrence relation">Recurrence relations</a> are equations which define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition (e.g., a <a href="Closed-form_expression" title="Closed-form expression">closed-form expression</a>).

</p><p>Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually the simplicity of instructions. The main disadvantage is that the memory usage of recursive algorithms may grow very quickly, rendering them impractical for larger instances.

</p>

<div class="mw-heading mw-heading2"><h2 id="In_biology">In biology</h2></div>

<p>Shapes that seem to have been created by recursive processes sometimes appear in plants and animals, such as in branching structures in which one large part branches out into two or more similar smaller parts. One example is <a href="Romanesco_broccoli" title="Romanesco broccoli">Romanesco broccoli</a>.<sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="In_the_social_sciences">In the social sciences</h2></div><p>

Authors use the concept of <i>recursivity</i> to foreground the situation in which specifically <i>social</i> scientists find themselves when producing knowledge about the world they are always already part of.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> According to Audrey Alejandro, “as social scientists, the recursivity of our condition deals with the fact that we are both subjects (as discourses are the medium through which we analyse) and objects of the academic discourses we produce (as we are social agents belonging to the world we analyse).”<sup id="cite_ref-Alejandro2021_19-0" class="reference"><a href="#cite_note-Alejandro2021-19"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup> From this basis, she identifies in recursivity a fundamental challenge in the production of emancipatory knowledge which calls for the exercise of <a href="Reflexivity_(social_theory)" title="Reflexivity (social theory)">reflexive</a> efforts:<style data-mw-deduplicate="TemplateStyles:r1244412712">

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style></p><blockquote class="templatequote"><p>we are socialised into discourses and dispositions produced by the socio-political order we aim to challenge, a socio-political order that we may, therefore, reproduce unconsciously while aiming to do the contrary. The recursivity of our situation as scholars – and, more precisely, the fact that the dispositional tools we use to produce knowledge about the world are themselves produced by this world – both evinces the vital necessity of implementing reflexivity in practice and poses the main challenge in doing so.</p></blockquote><div class="templatequotecite"><p style="display: inline; padding-left: 2.3em;">— Audrey Alejandro, <a href="#CITEREFAlejandro2021">Alejandro (2021)</a></p></div>

<div class="mw-heading mw-heading2"><h2 id="In_business">In business</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Management_cybernetics" title="Management cybernetics">Management cybernetics</a></div>

<p>Recursion is sometimes referred to in <a href="Management_science" title="Management science">management science</a> as the process of iterating through levels of abstraction in large business entities.<sup id="cite_ref-20" class="reference"><a href="#cite_note-20"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> A common example is the recursive nature of management <a href="Hierarchy" title="Hierarchy">hierarchies</a>, ranging from <a href="Line_management" title="Line management">line management</a> to <a href="Senior_management" title="Senior management">senior management</a> via <a href="Middle_management" title="Middle management">middle management</a>. It also encompasses the larger issue of <a href="Capital_structure" title="Capital structure">capital structure</a> in <a href="Corporate_governance" title="Corporate governance">corporate governance</a>.<sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>21<span class="cite-bracket">]</span></a></sup>

</p>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Mathematics_and_art" title="Mathematics and art">Mathematics and art</a> and <a href="Infinity_mirror" title="Infinity mirror">Infinity mirror</a></div>

<p>The <a href="Matryoshka_doll" title="Matryoshka doll">Matryoshka doll</a> is a physical artistic example of the recursive concept.<sup id="cite_ref-22" class="reference"><a href="#cite_note-22"><span class="cite-bracket">[</span>22<span class="cite-bracket">]</span></a></sup>

</p><p>Recursion has been used in paintings since <a href="Giotto" title="Giotto">Giotto</a>'s <i><a href="Stefaneschi_Triptych" title="Stefaneschi Triptych">Stefaneschi Triptych</a></i>, made in 1320. Its central panel contains the kneeling figure of Cardinal Stefaneschi, holding up the triptych itself as an offering.<sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>23<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>24<span class="cite-bracket">]</span></a></sup> This practice is more generally known as the <a href="Droste_effect" title="Droste effect">Droste effect</a>, an example of the <a href="Mise_en_abyme" title="Mise en abyme">Mise en abyme</a> technique.

</p><p><a href="M._C._Escher" title="M. C. Escher">M. C. Escher</a>'s <i><a href="Print_Gallery_(M._C._Escher)" title="Print Gallery (M. C. Escher)">Print Gallery</a></i> (1956) is a print which depicts a distorted city containing a gallery which <a href="Recursive" class="mw-redirect" title="Recursive">recursively</a> contains the picture, and so <i><a href="Ad_infinitum" title="Ad infinitum">ad infinitum</a></i>.<sup id="cite_ref-25" class="reference"><a href="#cite_note-25"><span class="cite-bracket">[</span>25<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="In_culture">In culture</h2></div>

<p>The film <i><a href="Inception" title="Inception">Inception</a></i> has colloquialized the appending of the suffix <i><a href="https://en.wiktionary.org/wiki/-ception" class="extiw external" title="wiktionary:-ception">-ception</a></i> to a noun to jokingly indicate the recursion of something.<sup id="cite_ref-26" class="reference"><a href="#cite_note-26"><span class="cite-bracket">[</span>26<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Corecursion" title="Corecursion">Corecursion</a> – Type of algorithm in computer science</li>

<li><a href="Course-of-values_recursion" title="Course-of-values recursion">Course-of-values recursion</a> – Technique for defining number-theoretic functions by recursion</li>

<li><a href="Digital_infinity" title="Digital infinity">Digital infinity</a> – Term in theoretical linguistics</li>

<li><a href="A_Dream_Within_a_Dream_(poem)" class="mw-redirect" title="A Dream Within a Dream (poem)">A Dream Within a Dream (poem)</a> – Poem by Edgar Allan Poe<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li>

<li><a href="Droste_effect" title="Droste effect">Droste effect</a> – Recursive visual effect</li>

<li><a href="False_awakening" title="False awakening">False awakening</a> – Vivid and convincing dream about awakening from sleep</li>

<li><a href="Fixed_point_combinator" class="mw-redirect" title="Fixed point combinator">Fixed point combinator</a> – Higher-order function Y for which Y f = f (Y f)<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li>

<li><a href="Infinite_compositions_of_analytic_functions" title="Infinite compositions of analytic functions">Infinite compositions of analytic functions</a> – Mathematical theory about infinitely iterated function composition</li>

<li><a href="Infinite_loop" title="Infinite loop">Infinite loop</a> – Programming idiom</li>

<li><a href="Infinite_regress" title="Infinite regress">Infinite regress</a> – Philosophical problem</li>

<li><a href="Infinitism" title="Infinitism">Infinitism</a> – Philosophical view that knowledge may be justified by an infinite chain of reasons</li>

<li><a href="Infinity_mirror" title="Infinity mirror">Infinity mirror</a> – Parallel mirrors reflecting each other</li>

<li><a href="Iterated_function" title="Iterated function">Iterated function</a> – Result of repeatedly applying a mathematical function</li>

<li><a href="Mathematical_induction" title="Mathematical induction">Mathematical induction</a> – Form of mathematical proof</li>

<li><a href="Mise_en_abyme" title="Mise en abyme">Mise en abyme</a> – Technique of placing a copy of an image within itself, or a story within a story</li>

<li><a href="Reentrant_(subroutine)" class="mw-redirect" title="Reentrant (subroutine)">Reentrant (subroutine)</a> – Concept in computer programming<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li>

<li><a href="Self-reference" title="Self-reference">Self-reference</a> – Sentence, idea or formula that refers to itself</li>

<li><a href="Spiegel_im_Spiegel" title="Spiegel im Spiegel">Spiegel im Spiegel</a> – 1978 musical composition by Arvo Pärt</li>

<li><a href="Strange_loop" title="Strange loop">Strange loop</a> – Cyclic structure that goes through several levels in a hierarchical system</li>

<li><a href="Tail_recursion" class="mw-redirect" title="Tail recursion">Tail recursion</a> – Subroutine call performed as final action of a procedure<span style="display:none" class="category-annotation-with-redirected-description">Pages displaying short descriptions of redirect targets</span></li>

<li><a href="Tupper's_self-referential_formula" title="Tupper's self-referential formula">Tupper's self-referential formula</a> – Formula that visually represents itself when graphed</li>

<li><a href="Turtles_all_the_way_down" title="Turtles all the way down">Turtles all the way down</a> – Statement of infinite regress</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFCausey2006" class="citation book cs1">Causey, Robert L. (2006). <i>Logic, sets, and recursion</i> (2nd ed.). Sudbury, Mass.: Jones and Bartlett Publishers. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7637-3784-4</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/62093042">62093042</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.britannica.com/science/Peano-axioms">"Peano axioms | mathematics"</a>. <i>Encyclopedia Britannica</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.merriam-webster.com/dictionary/recursive">"Definition of RECURSIVE"</a>. <i>www.merriam-webster.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFPinker1994" class="citation book cs1">Pinker, Steven (1994). <i>The Language Instinct</i>. William Morrow.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFPinkerJackendoff2005" class="citation journal cs1">Pinker, Steven; Jackendoff, Ray (2005). "The faculty of language: What's so special about it?". <i>Cognition</i>. <b>95</b> (2): <span class="nowrap">201–</span>236. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.116.7784">10.1.1.116.7784</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.cognition.2004.08.004">10.1016/j.cognition.2004.08.004</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/15694646">15694646</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1599505">1599505</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFNordquist" class="citation web cs1">Nordquist, Richard. <a rel="nofollow" class="external text" href="https://www.thoughtco.com/recursion-grammar-1691901">"What Is Recursion in English Grammar?"</a>. <i>ThoughtCo</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFNevinsPesetskyRodrigues2009" class="citation journal cs1">Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120106154616/http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf">"Evidence and argumentation: A reply to Everett (2009)"</a> <span class="cs1-format">(PDF)</span>. <i>Language</i>. <b>85</b> (3): <span class="nowrap">671–</span>681. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1353%2Flan.0.0140">10.1353/lan.0.0140</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16915455">16915455</a>. Archived from <a rel="nofollow" class="external text" href="http://web.mit.edu/linguistics/people/faculty/pesetsky/Nevins_Pesetsky_Rodrigues_2_Evidence_and_Argumentation_Reply_to_Everett.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2012-01-06.</cite></span>

</li>

<li id="cite_note-Drucker2008-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-Drucker2008_8-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFDrucker2008" class="citation book cs1">Drucker, Thomas (4 January 2008). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=R70M4zsVgREC&pg=PA110"><i>Perspectives on the History of Mathematical Logic</i></a>. Springer Science & Business Media. p. 110. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8176-4768-1</bdi>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., <i>Meaning, Use, and Interpretation of Language</i>. Reprinted in Paul Portner and Barbara Partee, eds. 2002. <i>Formal Semantics: The Essential Readings</i>. Blackwell.</span>

</li>

<li id="cite_note-ns02-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-ns02_10-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFNederhofSatta2002" class="citation cs2">Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", <i>Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02)</i>, Stroudsburg, PA, USA: Association for Computational Linguistics, pp. <span class="nowrap">112–</span>119, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.3115%2F1073083.1073104">10.3115/1073083.1073104</a></span></cite>.</span>

</li>

<li id="cite_note-Hunter-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-Hunter_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Hunter_11-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHunter2011" class="citation book cs1">Hunter, David (2011). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=kuwhTxCVovQC&q=recursion+joke"><i>Essentials of Discrete Mathematics</i></a>. Jones and Bartlett. p. 494. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781449604424</bdi>.</cite></span>

</li>

<li id="cite_note-Grainger_College-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-Grainger_College_12-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFShaffer" class="citation web cs1">Shaffer, Eric. <a rel="nofollow" class="external text" href="https://courses.engr.illinois.edu/cs173/sp2009/Lectures/lect_19.pdf">"CS 173:Discrete Structures"</a> <span class="cs1-format">(PDF)</span>. University of Illinois at Urbana-Champaign<span class="reference-accessdate">. Retrieved <span class="nowrap">7 July</span> 2023</span>.</cite></span>

</li>

<li id="cite_note-Columbia_University-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-Columbia_University_13-0">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.cs.columbia.edu/~bert/courses/1003/lecture8.pdf">"Introduction to Computer Science and Programming in C; Session 8: September 25, 2008"</a> <span class="cs1-format">(PDF)</span>. Columbia University<span class="reference-accessdate">. Retrieved <span class="nowrap">7 July</span> 2023</span>.</cite></span>

</li>

<li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.google.com/search?q=recursion">"recursion - Google Search"</a>. <i>www.google.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2019-10-24</span></span>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text">A. Kanamori, "<a rel="nofollow" class="external text" href="https://math.bu.edu/people/aki/20.pdf">In Praise of Replacement</a>", pp.50--52. Bulletin of Symbolic Logic, vol. 18, no. 1 (2012). Accessed 21 August 2023.</span>

</li>

<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://twistedsifter.com/2012/12/fractal-cauliflower-romanesco-broccoli/">"Picture of the Day: Fractal Cauliflower"</a>. 28 December 2012<span class="reference-accessdate">. Retrieved <span class="nowrap">19 April</span> 2020</span>.</cite></span>

</li>

<li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><cite id="CITEREFBourdieu1992" class="citation journal cs1">Bourdieu, Pierre (1992). "Double Bind et Conversion". <i>Pour Une Anthropologie Réflexive</i>. Paris: Le Seuil.</cite></span>

</li>

<li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><cite id="CITEREFGiddens1987" class="citation book cs1">Giddens, Anthony (1987). <i>Social Theory and Modern Sociology</i>. Polity Press.</cite></span>

</li>

<li id="cite_note-Alejandro2021-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-Alejandro2021_19-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFAlejandro2021" class="citation journal cs1">Alejandro, Audrey (2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F1354066120969789">"Reflexive discourse analysis: A methodology for the practice of reflexivity"</a>. <i><a href="European_Journal_of_International_Relations" title="European Journal of International Relations">European Journal of International Relations</a></i>. <b>27</b> (1): 171. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F1354066120969789">10.1177/1354066120969789</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1354-0661">1354-0661</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:229461433">229461433</a>.</cite></span>

</li>

<li id="cite_note-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-20">^</a></b></span> <span class="reference-text"><cite id="CITEREFRidingHainesThomas1994" class="citation journal cs1">Riding, Allan; Haines, George H.; Thomas, Roland (1994). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://journals.sagepub.com/doi/pdf/10.1177/104225879401800401">"The Canadian Small Business–Bank Interface: A Recursive Model"</a></span>. <i>Entrepreneurship Theory and Practice</i>. <b>18</b> (4). SAGE Journals: <span class="nowrap">5–</span>24. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1177%2F104225879401800401">10.1177/104225879401800401</a>.</cite></span>

</li>

<li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><cite id="CITEREFBeer1972" class="citation book cs1">Beer, Stafford (1972). <i>Brain Of The Firm</i>. John Wiley & Sons. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0471948391</bdi>.</cite></span>

</li>

<li id="cite_note-22"><span class="mw-cite-backlink"><b><a href="#cite_ref-22">^</a></b></span> <span class="reference-text"><cite id="CITEREFTang" class="citation web cs1">Tang, Daisy. <a rel="nofollow" class="external text" href="http://www.cpp.edu/~ftang/courses/CS240/lectures/recursion.htm">"Recursion"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">24 September</span> 2015</span>. <q>More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.</q></cite></span>

</li>

<li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://mv.vatican.va/3_EN/pages/PIN/PIN_Sala02_03.html">"Giotto di Bondone and assistants: Stefaneschi triptych"</a>. The Vatican<span class="reference-accessdate">. Retrieved <span class="nowrap">16 September</span> 2015</span>.</cite></span>

</li>

<li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><cite id="CITEREFSvozil2018" class="citation book cs1">Svozil, Karl (2018). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=gxBMDwAAQBAJ&pg=PA12"><i>Physical (A)Causality: Determinism, Randomness and Uncaused Events</i></a>. Springer. p. 12. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783319708157</bdi>.</cite></span>

</li>

<li id="cite_note-25"><span class="mw-cite-backlink"><b><a href="#cite_ref-25">^</a></b></span> <span class="reference-text"><cite id="CITEREFCooper2007" class="citation web cs1">Cooper, Jonathan (5 September 2007). <a rel="nofollow" class="external text" href="https://unwrappingart.com/art/art-and-mathematics/">"Art and Mathematics"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">5 July</span> 2020</span>.</cite></span>

</li>

<li id="cite_note-26"><span class="mw-cite-backlink"><b><a href="#cite_ref-26">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://neologisms.rice.edu/index.php?a=term&d=1&t=17573">"-ception – The Rice University Neologisms Database"</a>. Rice University. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170705153941/http://neologisms.rice.edu/index.php?a=term&d=1&t=17573">Archived</a> from the original on July 5, 2017<span class="reference-accessdate">. Retrieved <span class="nowrap">December 23,</span> 2016</span>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .refbegin{margin-bottom:0.5em}.mw-parser-output .refbegin-hanging-indents>ul{margin-left:0}.mw-parser-output .refbegin-hanging-indents>ul>li{margin-left:0;padding-left:3.2em;text-indent:-3.2em}.mw-parser-output .refbegin-hanging-indents ul,.mw-parser-output .refbegin-hanging-indents ul li{list-style:none}@media(max-width:720px){.mw-parser-output .refbegin-hanging-indents>ul>li{padding-left:1.6em;text-indent:-1.6em}}.mw-parser-output .refbegin-columns{margin-top:0.3em}.mw-parser-output .refbegin-columns ul{margin-top:0}.mw-parser-output .refbegin-columns li{page-break-inside:avoid;break-inside:avoid-column}@media screen{.mw-parser-output .refbegin{font-size:90%}}

/* end https://en.wikipedia.org/ */

</style><div class="refbegin" style="">

<ul><li><cite id="CITEREFDijkstra1960" class="citation journal cs1"><a href="Edsger_W._Dijkstra" title="Edsger W. Dijkstra">Dijkstra, Edsger W.</a> (1960). "Recursive Programming". <i>Numerische Mathematik</i>. <b>2</b> (1): <span class="nowrap">312–</span>318. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01386232">10.1007/BF01386232</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:127891023">127891023</a>.</cite></li>

<li><cite id="CITEREFJohnsonbaugh,_Richard2004" class="citation book cs1"><a href="Richard_Johnsonbaugh" title="Richard Johnsonbaugh">Johnsonbaugh, Richard</a> (2004). <i>Discrete Mathematics</i>. Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-117686-7</bdi>.</cite></li>

<li><cite id="CITEREFHofstadter,_Douglas1999" class="citation book cs1"><a href="Douglas_Hofstadter" title="Douglas Hofstadter">Hofstadter, Douglas</a> (1999). <a rel="nofollow" class="external text" href="https://archive.org/details/gdelescherbachet00hofs"><i>Gödel, Escher, Bach: an Eternal Golden Braid</i></a>. Basic Books. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-465-02656-2</bdi>.</cite></li>

<li><cite id="CITEREFShoenfield,_Joseph_R.2000" class="citation book cs1"><a href="Joseph_R._Shoenfield" title="Joseph R. Shoenfield">Shoenfield, Joseph R.</a> (2000). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/recursiontheory0000shoe"><i>Recursion Theory</i></a></span>. A K Peters Ltd. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-56881-149-9</bdi>.</cite></li>

<li><cite id="CITEREFCausey,_Robert_L.2001" class="citation book cs1"><a href="Causey%2C_Robert_L." class="mw-redirect" title="Causey, Robert L.">Causey, Robert L.</a> (2001). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/logicsetsrecursi0000caus"><i>Logic, Sets, and Recursion</i></a></span>. Jones & Bartlett. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7637-1695-0</bdi>.</cite></li>

<li><cite id="CITEREFCori,_ReneLascar,_DanielPelletier,_Donald_H.2001" class="citation book cs1">Cori, Rene; Lascar, Daniel; Pelletier, Donald H. (2001). <i>Recursion Theory, Gödel's Theorems, Set Theory, Model Theory</i>. Oxford University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-19-850050-6</bdi>.</cite></li>

<li><cite id="CITEREFBarwise,_JonMoss,_Lawrence_S.1996" class="citation book cs1"><a href="Jon_Barwise" title="Jon Barwise">Barwise, Jon</a>; Moss, Lawrence S. (1996). <i>Vicious Circles</i>. Stanford Univ Center for the Study of Language and Information. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-19-850050-6</bdi>.</cite> - offers a treatment of <a href="Corecursion" title="Corecursion">corecursion</a>.</li>

<li><cite id="CITEREFRosen,_Kenneth_H.2002" class="citation book cs1">Rosen, Kenneth H. (2002). <i>Discrete Mathematics and Its Applications</i>. McGraw-Hill College. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-07-293033-7</bdi>.</cite></li>

<li><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs1">Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). <i>Introduction to Algorithms</i>. Mit Pr. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-03293-3</bdi>.</cite></li>

<li><cite id="CITEREFKernighan,_B.Ritchie,_D.1988" class="citation book cs1">Kernighan, B.; Ritchie, D. (1988). <a rel="nofollow" class="external text" href="https://archive.org/details/cprogramminglang00bria"><i>The C programming Language</i></a>. Prentice Hall. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-110362-7</bdi>.</cite></li>

<li><cite id="CITEREFStokey,_NancyRobert_LucasEdward_Prescott1989" class="citation book cs1">Stokey, Nancy; Robert Lucas; Edward Prescott (1989). <i>Recursive Methods in Economic Dynamics</i>. Harvard University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-674-75096-8</bdi>.</cite></li>

<li><cite id="CITEREFHungerford1980" class="citation book cs1">Hungerford (1980). <i>Algebra</i>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-90518-1</bdi>.</cite>, first chapter on set theory.</li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Recursion" class="extiw external" title="commons:Category:Recursion">Recursion</a></span>.</div></div>

</div>

<div class="side-box-text plainlist">Look up <i><b><a href="https://en.wiktionary.org/wiki/recursion" class="extiw external" title="wiktionary:recursion">recursion</a></b></i> or <i><b><a href="https://en.wiktionary.org/wiki/recursivity" class="extiw external" title="wiktionary:recursivity">recursivity</a></b></i> in Wiktionary, the free dictionary.</div></div>

</div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20050206051223/http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm">Recursion</a> - tutorial by Alan Gauld</li>

<li><a rel="nofollow" class="external text" href="http://research.swtch.com/2010/03/zip-files-all-way-down.html">Zip Files All The Way Down</a></li>

<li><a rel="nofollow" class="external text" href="http://www.ucl.ac.uk/psychlangsci/staff/linguistics-staff/nevins-publications/npr09b">Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009)</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Fractals328" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Fractals328" style="font-size:114%;margin:0 4em"><a href="Fractal" title="Fractal">Fractals</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Characteristics</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fractal_dimension" title="Fractal dimension">Fractal dimensions</a>

<ul><li><a href="Assouad_dimension" title="Assouad dimension">Assouad</a></li>

<li><a href="Minkowski%E2%80%93Bouligand_dimension" title="Minkowski–Bouligand dimension">Box-counting</a>

<ul><li><a href="Higuchi_dimension" title="Higuchi dimension">Higuchi</a></li></ul></li>

<li><a href="Correlation_dimension" title="Correlation dimension">Correlation</a></li>

<li><a href="Hausdorff_dimension" title="Hausdorff dimension">Hausdorff</a></li>

<li><a href="Packing_dimension" title="Packing dimension">Packing</a></li>

<li><a href="Lebesgue_covering_dimension" title="Lebesgue covering dimension">Topological</a></li></ul></li>

<li><a href="Self-similarity" title="Self-similarity">Self-similarity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Iterated_function_system" title="Iterated function system">Iterated function <br>system</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Barnsley_fern" title="Barnsley fern">Barnsley fern</a></li>

<li><a href="Cantor_set" title="Cantor set">Cantor set</a></li>

<li><a href="Koch_snowflake" title="Koch snowflake">Koch snowflake</a></li>

<li><a href="Menger_sponge" title="Menger sponge">Menger sponge</a></li>

<li><a href="Sierpi%C5%84ski_carpet" title="Sierpiński carpet">Sierpiński carpet</a></li>

<li><a href="Sierpi%C5%84ski_triangle" title="Sierpiński triangle">Sierpiński triangle</a></li>

<li><a href="Apollonian_gasket" title="Apollonian gasket">Apollonian gasket</a></li>

<li><a href="Fibonacci_word_fractal" title="Fibonacci word fractal">Fibonacci word</a></li>

<li><a href="Space-filling_curve" title="Space-filling curve">Space-filling curve</a>

<ul><li><a href="Blancmange_curve" title="Blancmange curve">Blancmange curve</a></li>

<li><a href="De_Rham_curve" title="De Rham curve">De Rham curve</a>

<ul><li><a href="Minkowski_sausage" title="Minkowski sausage">Minkowski</a></li></ul></li>

<li><a href="Dragon_curve" title="Dragon curve">Dragon curve</a></li>

<li><a href="Hilbert_curve" title="Hilbert curve">Hilbert curve</a></li>

<li><a href="Koch_snowflake" title="Koch snowflake">Koch curve</a></li>

<li><a href="L%C3%A9vy_C_curve" title="Lévy C curve">Lévy C curve</a></li>

<li><a href="Moore_curve" title="Moore curve">Moore curve</a></li>

<li><a href="Peano_curve" title="Peano curve">Peano curve</a></li>

<li><a href="Sierpi%C5%84ski_curve" title="Sierpiński curve">Sierpiński curve</a></li>

<li><a href="Z-order_curve" title="Z-order curve">Z-order curve</a></li></ul></li>

<li><a href="Fractal_string" title="Fractal string">String</a></li>

<li><a href="T-square_(fractal)" title="T-square (fractal)">T-square</a></li>

<li><a href="N-flake" title="N-flake">n-flake</a></li>

<li><a href="Vicsek_fractal" title="Vicsek fractal">Vicsek fractal</a></li>

<li><a href="Gosper_curve" title="Gosper curve">Gosper curve</a></li>

<li><a href="Pythagoras_tree_(fractal)" title="Pythagoras tree (fractal)">Pythagoras tree</a></li>

<li><a href="Weierstrass_function" title="Weierstrass function">Weierstrass function</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Attractor#Strange_attractor" title="Attractor">Strange attractor</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multifractal_system" title="Multifractal system">Multifractal system</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="L-system" title="L-system">L-system</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fractal_canopy" title="Fractal canopy">Fractal canopy</a></li>

<li><a href="Space-filling_curve" title="Space-filling curve">Space-filling curve</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Fractal#Common_techniques_for_generating_fractals" title="Fractal">Escape-time <br>fractals</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Burning_Ship_fractal" title="Burning Ship fractal">Burning Ship fractal</a></li>

<li><a href="Julia_set" title="Julia set">Julia set</a>

<ul><li><a href="Filled_Julia_set" title="Filled Julia set">Filled</a></li>

<li><a href="Newton_fractal" title="Newton fractal">Newton fractal</a></li>

<li><a href="Douady_rabbit" title="Douady rabbit">Douady rabbit</a></li></ul></li>

<li><a href="Lyapunov_fractal" title="Lyapunov fractal">Lyapunov fractal</a></li>

<li><a href="Mandelbrot_set" title="Mandelbrot set">Mandelbrot set</a>

<ul><li><a href="Misiurewicz_point" title="Misiurewicz point">Misiurewicz point</a></li></ul></li>

<li><a href="Multibrot_set" title="Multibrot set">Multibrot set</a></li>

<li><a href="Newton_fractal" title="Newton fractal">Newton fractal</a></li>

<li><a href="Tricorn_(mathematics)" title="Tricorn (mathematics)">Tricorn</a></li>

<li><a href="Mandelbox" title="Mandelbox">Mandelbox</a></li>

<li><a href="Mandelbulb" title="Mandelbulb">Mandelbulb</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Rendering_(computer_graphics)" title="Rendering (computer graphics)">Rendering</a> techniques</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Buddhabrot" title="Buddhabrot">Buddhabrot</a></li>

<li><a href="Orbit_trap" title="Orbit trap">Orbit trap</a></li>

<li><a href="Pickover_stalk" title="Pickover stalk">Pickover stalk</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Chaos_game" title="Chaos game">Random</a> fractals</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Brownian_motion" title="Brownian motion">Brownian motion</a>

<ul><li><a href="Diffusion-limited_aggregation" title="Diffusion-limited aggregation">Brownian tree</a></li>

<li><a href="Brownian_motor" title="Brownian motor">Brownian motor</a></li></ul></li>

<li><a href="Fractal_landscape" title="Fractal landscape">Fractal landscape</a></li>

<li><a href="L%C3%A9vy_flight" title="Lévy flight">Lévy flight</a></li>

<li><a href="Percolation_theory" title="Percolation theory">Percolation theory</a></li>

<li><a href="Self-avoiding_walk" title="Self-avoiding walk">Self-avoiding walk</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">People</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Michael_Barnsley" title="Michael Barnsley">Michael Barnsley</a></li>

<li><a href="Georg_Cantor" title="Georg Cantor">Georg Cantor</a></li>

<li><a href="Bill_Gosper" title="Bill Gosper">Bill Gosper</a></li>

<li><a href="Felix_Hausdorff" title="Felix Hausdorff">Felix Hausdorff</a></li>

<li><a href="Desmond_Paul_Henry" title="Desmond Paul Henry">Desmond Paul Henry</a></li>

<li><a href="Gaston_Julia" title="Gaston Julia">Gaston Julia</a></li>

<li><a href="Niels_Fabian_Helge_von_Koch" title="Niels Fabian Helge von Koch">Niels Fabian Helge von Koch</a></li>

<li><a href="Aleksandr_Lyapunov" title="Aleksandr Lyapunov">Aleksandr Lyapunov</a></li>

<li><a href="Benoit_Mandelbrot" title="Benoit Mandelbrot">Benoit Mandelbrot</a></li>

<li><a href="Hamid_Naderi_Yeganeh" title="Hamid Naderi Yeganeh">Hamid Naderi Yeganeh</a></li>

<li><a href="Lewis_Fry_Richardson" title="Lewis Fry Richardson">Lewis Fry Richardson</a></li>

<li><a href="Wac%C5%82aw_Sierpi%C5%84ski" title="Wacław Sierpiński">Wacław Sierpiński</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Coastline_paradox" title="Coastline paradox">Coastline paradox</a></li>

<li><a href="Fractal_art" title="Fractal art">Fractal art</a></li>

<li><a href="List_of_fractals_by_Hausdorff_dimension" title="List of fractals by Hausdorff dimension">List of fractals by Hausdorff dimension</a></li>

<li><i><a href="The_Fractal_Geometry_of_Nature" title="The Fractal Geometry of Nature">The Fractal Geometry of Nature</a></i> (1982 book)</li>

<li><i><a href="The_Beauty_of_Fractals" title="The Beauty of Fractals">The Beauty of Fractals</a></i> (1986 book)</li>

<li><i><a href="Chaos%3A_Making_a_New_Science" title="Chaos: Making a New Science">Chaos: Making a New Science</a></i> (1987 book)</li>

<li><a href="Kaleidoscope" title="Kaleidoscope">Kaleidoscope</a></li>

<li><a href="Chaos_theory" title="Chaos theory">Chaos theory</a></li></ul>

</div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic344" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Mathematical_logic344" style="font-size:114%;margin:0 4em"><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Axiom" title="Axiom">Axiom</a>

<li><a href="Cardinality" title="Cardinality">Cardinality</a></li>

<li><a href="First-order_logic" title="First-order logic">First-order logic</a></li>

<li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li>

<li><a href="Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (list)<br> and <a href="Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="G%C3%B6del's_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="G%C3%B6del's_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li>

<li><a href="Tarski's_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li>

<li><a href="Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li>

<li>Cantor's <a href="Cantor's_theorem" title="Cantor's theorem">theorem,</a> <a href="Cantor's_paradox" title="Cantor's paradox">paradox</a> and <a href="Cantor's_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li>

<li><a href="Compactness_theorem" title="Compactness theorem">Compactness</a></li>

<li><a href="Halting_problem" title="Halting problem">Halting problem</a></li>

<li><a href="Lindstr%C3%B6m's_theorem" title="Lindström's theorem">Lindström's</a></li>

<li><a href="L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li>

<li><a href="Russell's_paradox" title="Russell's paradox">Russell's paradox</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_logic" title="Classical logic">Classical logic</a></li>

<li><a href="Logical_truth" title="Logical truth">Logical truth</a></li>

<li><a href="Tautology_(logic)" title="Tautology (logic)">Tautology</a></li>

<li><a href="Proposition" title="Proposition">Proposition</a></li>

<li><a href="Inference" title="Inference">Inference</a></li>

<li><a href="Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li>

<li><a href="Consistency" title="Consistency">Consistency</a>

<ul><li><a href="Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li>

<li><a href="Argument" title="Argument">Argument</a></li>

<li><a href="Soundness" title="Soundness">Soundness</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li>

<li><a href="Syllogism" title="Syllogism">Syllogism</a></li>

<li><a href="Square_of_opposition" title="Square of opposition">Square of opposition</a></li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Boolean_function" title="Boolean function">Boolean functions</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connectives</a></li>

<li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li>

<li><a href="Propositional_formula" title="Propositional formula">Propositional formula</a></li>

<li><a href="Truth_table" title="Truth table">Truth tables</a></li>

<li><a href="Many-valued_logic" title="Many-valued logic">Many-valued logic</a>

<li><a href="Finite-valued_logic" title="Finite-valued logic">finite</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-order_logic" title="First-order logic">First-order</a>

<li><a href="Second-order_logic" title="Second-order logic">Second-order</a>

<ul><li><a href="Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li>

<li><a href="Higher-order_logic" title="Higher-order logic">Higher-order</a></li>

<li><a href="Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li>

<li><a href="Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li>

<li><a href="Class_(set_theory)" title="Class (set theory)">Class</a></li>

<li>(<a href="Urelement" title="Urelement">Ur-</a>)<a href="Element_(mathematics)" title="Element (mathematics)">Element</a></li>

<li><a href="Ordinal_number" title="Ordinal number">Ordinal number</a></li>

<li><a href="Extensionality" title="Extensionality">Extensionality</a></li>

<li><a href="Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li>

<li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a>

<ul><li><a href="Equivalence_relation" title="Equivalence relation">equivalence</a></li>

<li><a href="Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li>

<li>Set operations:

<ul><li><a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li>

<li><a href="Union_(set_theory)" title="Union (set theory)">union</a></li>

<li><a href="Complement_(set_theory)" title="Complement (set theory)">complement</a></li>

<li><a href="Cartesian_product" title="Cartesian product">Cartesian product</a></li>

<li><a href="Power_set" title="Power set">power set</a></li>

<li><a href="List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Countable_set" title="Countable set">Countable</a></li>

<li><a href="Uncountable_set" title="Uncountable set">Uncountable</a></li>

<li><a href="Empty_set" title="Empty set">Empty</a></li>

<li><a href="Inhabited_set" title="Inhabited set">Inhabited</a></li>

<li><a href="Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li>

<li><a href="Finite_set" title="Finite set">Finite</a></li>

<li><a href="Infinite_set" title="Infinite set">Infinite</a></li>

<li><a href="Transitive_set" title="Transitive set">Transitive</a></li>

<li><a href="Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li>

<li><a href="Fuzzy_set" title="Fuzzy set">Fuzzy</a></li>

<li><a href="Universal_set" title="Universal set">Universal</a></li>

<li><a href="Universe_(mathematics)" title="Universe (mathematics)">Universe</a>

<ul><li><a href="Constructible_universe" title="Constructible universe">constructible</a></li>

<li><a href="Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li>

<li><a href="Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="Map_(mathematics)" title="Map (mathematics)">Map</a>

<ul><li><a href="Domain_of_a_function" title="Domain of a function">domain</a></li>

<li><a href="Codomain" title="Codomain">codomain</a></li>

<li><a href="Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li>

<li><a href="Injective_function" title="Injective function">In</a>/<a href="Surjective_function" title="Surjective function">Sur</a>/<a href="Bijection" title="Bijection">Bi</a>-jection</li>

<li><a href="Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li>

<li><a href="Isomorphism" title="Isomorphism">Isomorphism</a></li>

<li><a href="G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Large_cardinal" title="Large cardinal">Large cardinal</a>

<ul><li><a href="Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li>

<li><a href="Aleph_number" title="Aleph number">Aleph number</a></li>

<li><a href="Operation_(mathematics)" title="Operation (mathematics)">Operation</a>

<ul><li><a href="Binary_operation" title="Binary operation">binary</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a>

<ul><li><a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li>

<li><a href="Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li>

<li><a href="General_set_theory" title="General set theory">General</a></li>

<li><a href="Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li>

<li><a href="Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li>

<li><a href="Naive_set_theory" title="Naive set theory">Naive</a></li>

<li><a href="New_Foundations" title="New Foundations">New Foundations</a></li>

<li><a href="Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li>

<li><a href="Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li>

<li><a href="Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li>

<li><a href="Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Formal_system" title="Formal system">Formal systems</a> (<a href="List_of_formal_systems" title="List of formal systems"><span style="font-size: 85%;">list</span></a>),<br><a href="Formal_language" title="Formal language">language</a> and <a href="Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li>

<li><a href="Arity" title="Arity">Arity</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata</a></li>

<li><a href="Axiom_schema" title="Axiom schema">Axiom schema</a></li>

<li><a href="Expression_(mathematics)" title="Expression (mathematics)">Expression</a>

<ul><li><a href="Ground_expression" title="Ground expression">ground</a></li></ul></li>

<li><a href="Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a>

<ul><li><a href="Extension_by_definitions" class="mw-redirect" title="Extension by definitions">by definition</a></li>

<li><a href="Conservative_extension" title="Conservative extension">conservative</a></li></ul></li>

<li><a href="Finitary_relation" title="Finitary relation">Relation</a></li>

<li><a href="Formation_rule" title="Formation rule">Formation rule</a></li>

<li><a href="Formal_grammar" title="Formal grammar">Grammar</a></li>

<li><a href="Well-formed_formula" title="Well-formed formula">Formula</a>

<ul><li><a href="Atomic_formula" title="Atomic formula">atomic</a></li>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li>

<li><a href="Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li>

<li><a href="Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li>

<li><a href="Formal_language" title="Formal language">Language</a></li>

<li><a href="Metalanguage" title="Metalanguage">Metalanguage</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connective</a>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a>

<ul><li><a href="Functional_predicate" title="Functional predicate">functional</a></li>

<li><a href="Predicate_variable" title="Predicate variable">variable</a></li>

<li><a href="Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li>

<li><a href="Formal_proof" title="Formal proof">Proof</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a>

<ul><li><a href="Atomic_sentence" title="Atomic sentence">atomic</a></li>

<li><a href="Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li>

<li><a href="Signature_(logic)" title="Signature (logic)">Signature</a></li>

<li><a href="String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li>

<li><a href="Substitution_(logic)" title="Substitution (logic)">Substitution</a></li>

<li><a href="Symbol_(formal)" title="Symbol (formal)">Symbol</a>

<ul><li><a href="Uninterpreted_function" title="Uninterpreted function">function</a></li>

<li><a href="Logical_constant" title="Logical constant">logical/constant</a></li>

<li><a href="Non-logical_symbol" title="Non-logical symbol">non-logical</a></li>

<li><a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><span class="nowrap">Example <a href="Axiomatic_system" title="Axiomatic system">axiomatic<br>systems</a> <span style="font-size: 85%;">(<a href="List_of_first-order_theories" title="List of first-order theories">list</a>)</span></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>of <a href="True_arithmetic" title="True arithmetic">arithmetic</a>:

<ul><li><a href="Peano_axioms" title="Peano axioms">Peano</a></li>

<li><a href="Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li>

<li><a href="Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li>

<li><a href="Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li>

<li><a href="Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li>

<li><a href="Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li>

<li>of the <a href="Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a>

<ul><li><a href="Tarski's_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li>

<li>of <a href="Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a>

<ul><li><a href="Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li>

<li><a href="Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li>

<li>of <a href="Foundations_of_geometry" title="Foundations of geometry">geometry</a>:

<ul><li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean</a>:

<ul><li><a href="Euclid's_Elements" title="Euclid's Elements"><i>Elements</i></a></li>

<li><a href="Hilbert's_axioms" title="Hilbert's axioms">Hilbert's</a></li>

<li><a href="Tarski's_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li>

<li><a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul>

<ul><li><i><a href="Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></i></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Natural_deduction" title="Natural deduction">Natural deduction</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Rule_of_inference" title="Rule of inference">Rule of inference</a></li>

<li><a href="Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Formal_system" title="Formal system">Systems</a>

<ul><li><a href="Axiomatic_system" title="Axiomatic system">axiomatic</a></li>

<li><a href="Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li>

<li><a href="Hilbert_system" title="Hilbert system">Hilbert</a>

<li><a href="Complete_theory" title="Complete theory">Complete theory</a></li>

<li><a href="Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li>

<li><a href="Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li>

<li><a href="Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li>

<li><a href="Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li>

<li><a href="Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a>

<ul><li><a href="Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li>

<li><a href="Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a>

<ul><li><a href="Elementary_equivalence" title="Elementary equivalence">equivalence</a></li>

<li><a href="Finite_model_theory" title="Finite model theory">finite</a></li>

<li><a href="Saturated_model" title="Saturated model">saturated</a></li>

<li><a href="Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li>

<li><a href="Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li>

<li><a href="Non-standard_model" title="Non-standard model">Non-standard model</a>

<ul><li><a href="Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li>

<li><a href="Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a>

<ul><li><a href="Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li>

<li><a href="Categorical_theory" title="Categorical theory">Categorical theory</a></li>

<li><a href="Model_complete_theory" title="Model complete theory">Model complete theory</a></li>

<li><a href="Satisfiability" title="Satisfiability">Satisfiability</a></li>

<li><a href="Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li>

<li><a href="Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li>

<li><a href="Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a>

<ul><li><a href="Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li>

<li><a href="Tarski's_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li>

<li><a href="Kripke's_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li>

<li><a href="T-schema" title="T-schema">T-schema</a></li>

<li><a href="Transfer_principle" title="Transfer principle">Transfer principle</a></li>

<li><a href="Truth_predicate" title="Truth predicate">Truth predicate</a></li>

<li><a href="Truth_value" title="Truth value">Truth value</a></li>

<li><a href="Ultraproduct" title="Ultraproduct">Ultraproduct</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Church_encoding" title="Church encoding">Church encoding</a></li>

<li><a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li>

<li><a href="Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li>

<li><a href="Computable_function" title="Computable function">Computable function</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Decision_problem" title="Decision problem">Decision problem</a>

<ul><li><a href="Decidability_(logic)" title="Decidability (logic)">decidable</a></li>

<li><a href="Undecidable_problem" title="Undecidable problem">undecidable</a></li>

<li><a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li>

<li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_logic" title="Abstract logic">Abstract logic</a></li>

<li><a href="Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li>

<li><a href="Category_theory" title="Category theory">Category theory</a></li>

<li><a href="Concrete_category" title="Concrete category">Concrete</a>/<a href="Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li>

<li><a href="Category_of_sets" title="Category of sets">Category of sets</a></li>

<li><a href="History_of_logic" title="History of logic">History of logic</a></li>

<li><a href="History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="Logicism" title="Logicism">Logicism</a></li>

<li><a href="Mathematical_object" title="Mathematical object">Mathematical object</a></li>

<li><a href="Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li>

<li><a href="Supertask" title="Supertask">Supertask</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><b><span class="nowrap"><span class="skin-invert-image noviewer" typeof="mw:File"></span> </span><a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></b></div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox authority-control" aria-label="Navbox390" style="padding:3px"><table class="nowraplinks hlist navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="row" class="navbox-group" style="width:1%">Authority control databases: National </th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><span class="uid"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4191814-9">Germany</a></span></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-18" href="https://en.wikipedia.org/wiki/?title=Recursion&oldid=1301188528">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>